1. Field of the Invention
This invention relates generally to so-called "artificial intelligence" (AI) systems, "expert systems" or "knowledge-based systems". The invention is more specifically related to the development and application of an expert knowledge base for use in the real time management of an automated factory.
2. Description of the Prior Art
So-called "expert systems" are often formed of computer hardware/software combinations which are structured to mimic the behavior of a human having expert knowledge in a particular field. The human expert provides guidelines for reasoning through problems within the expert's field and these guidelines are transformed into a set of "if-then" rule constructs. The latter constructs may be expressed in software and/or hardware but are most typically expressed in software using an AI language such as LISP or PROLOG. A compilation of if-then constructs forms a so called "knowledge base" or "rule base". The knowledge base (rule-base) is normally programmed into the memory of a suitable computer in the form of a LISP or PROLOG compatible "data base" in order to provide the computer with welldefined symbol processing rules for deriving by means of "inferencing", answers to real-world questions. Inferenced answers are derived on the basis of both the transformed guideline-knowledge of the human expert and on "facts" that are established (inferred) from sensing the real world. For a generalized explanation of artificial intelligence, the reader is directed to references such as "Introduction to Artificial Intelligence", Eugene Charniah and Drew McDermott, Addison Wesley Publishing Company, 1985 and "Building Expert Systems", F. Hayes-Roth, D. A. Waterman and D. B. Lenat, Editors, Addision-Wesley Publishing Company, 1983.
Examples of systems employing expert-system technology are disclosed in: (a) U.S. Pat. No. 4,783,752, "Knowledge Based Processor for Application Programs Using Conventional DataProcessing Capabilities" issued Nov. 8, 1988 to Kaplan et al.; (b) U.S. Pat. No. 4,779,208, "Information Processing System and Method for Use In Computer Systems Suitable for Production System" issued Oct. 18, 1988 to Tsuruta et al.; (c) U.S. Pat. No. 4,704,695, "Inference System" issued Nov. 3, 1987 to Kimura et al.; (d) U.S. Pat. No. 4,675,829, "Method and Apparatus for Building Knowledge-Based Systems" issued Jun. 23, 1987 to Clemenson; (e) U.S. Pat. No. 4,642,782, "Rule Based Diagnostic System With Dynamic Alteration Capability" issued Feb. 10, 1987 to Kemper et al.; and (f) U.S. Pat. No. 4,591,983, "Hierarchical Knowledge System" issued May 27, 1986 to Bennett et al. The disclosures of these patents (a-f) are incorporated herein by reference.
Expert-system technology can be employed in an unlimited number of applications. By way of example, the technology can be applied for creating an intelligent gameplaying machine which mimics the behavior of an expert gameplayer such as a chess master, for creating an automated instruction machine which mimics the instructional behavior of a college professor or for creating a medical diagnosis machine which mimics the behavior of a trained medical specialist (i.e., the EMYCIN system developed at Stanford University, California).
In many such applications, the expert system is not expected to perform the operations of analyzing received information and arriving at expert conclusions any faster than its human counterpart. In some instances, the expert system is permitted to take substantially more time to arrive at conclusions than its human counterpart. There are few, if any, time-imposed constraints created in these cases on the strategies that may be adopted for artificially imitating human intelligence. As a result, the information processing speed of an underlying (supporting) computer is not a crucial factor and neither is the real-time speed of the computer algorithm which provides the computer with its artificial intelligence (AI). Relatively generic types of symbol manipulation algorithms can be freely developed to solve problems for such cases. Examples of general-purpose expert "shells" include the Nexpert.TM. software package of Neuron Data Inc. and the Sl.TM. and Ml.TM. software packages available from Tecknowledge Inc.
There is a class of situations where time and speed are important; where it is desirable to have the ability to analyze large volumes of data and arrive quickly at expert-type conclusions at speeds substantially faster than a human expert. The real time management of a high speed factory production line, where the latter is to be automated to process a large volume of workproduct through a large number of simultaneously-operating workstations, is one example of this class of situations.
It has been proposed that expert-system technology should be applied to the real time management of automated factories such as factories which employ robots (intelligent production machines) for the assembly of products.
Modern factories are often arranged to have a large number of automated workstations (i.e., 10, 100 or more different pieces of robotic production equipment) disposed in array fashion on a production floor. Typically, each workstation is configured for a highly specialized task (i.e., welding, drilling, sewing, etc.) and its operation is controlled by a specially and individually programmed computer control system. The latter computer control system of each specialized workstation is often referred to in the trade as a "programmable logic controller" or more simply, a PLC. Examples of PLC's are disclosed in U.S. Pat. No. 4,365,297, "Industrial Control System With Distributed Computer Implemented Logic", issued Dec. 21, 1982, to Grisham Jr. et al. and in U.S. Pat. No. 4,270,184, "Microprocessor-Based Programmable Logic Controller" issued May 26, 1981, to Shimokawa et al. The disclosures of these patents are incorporated herein by reference. PLC's are commercially available from companies such as Allen-Bradely Inc. of Cleveland, Ohio and Modicon Inc. of North Andover, Massachusetts under the respective tradenames of A-B PLC-2/30 Processor.TM. and Micro-84.TM..
The development of an automated management system for managing a large sized array of PLC controlled equipment can pose a complex challenge. By way of example, let it be assumed that a factory production line comprises a large number (i.e., ten or more) of differently configured workstations including automated drilling machines, welding machines, component insertion machines, polishing machines, painting machines and so forth. Let it further be assumed that workpieces can be programmably routed from one station to another as desired to provide a wide variety of machining sequences. (An automated routing system having the ability to route objects through a complex conveyance maze is disclosed in U.S. Pat. No. 4,512,747 issued Apr. 23, 1985 to Hitchens, which disclosure is incorporated herein by reference.)
Let it be presumed that if one of the workstations malfunctions or needs to be shut down, it will often be possible to maintain flow on the production line by changing the machining sequence of the line so as to temporarily circumvent the malfunctioning workstation and to complete the manufacturing process by later returning workpieces to the circumvented workstation after the malfunction is corrected. But also let it be assumed that there will be complications to such circumvention. For the sake of example, let it be supposed that if the malfunctioning workstation cannot be fixed within a given period of time, it is preferable to shut down the entire production line rather than to allow a large inventory of unfinished parts (for which storage space is not available) to accumulate around the malfunctioning workstation.
Given this scenario, let it be further assumed that the PLC's of all workstations on the production line are coupled via a local area network (LAN) to a computerized central management system and that the latter system is expected to intelligently manage the production floor and cope with emergent problems in the same manner as would an intelligent human manager (expert), but at much higher speeds.
Under such a postulated situation, the following problem can be posed. What operations should the central management system perform if it unexpectedly receives a message from the PLC (programmable logic controller) of a component inserting machine, X, indicating that the inserting machine X has run out of stock? It could be that the out-of-stock message is in error (i.e., due to a faulty sensor in machine X) and that no action needs to be taken. On the other hand, if the message is correct, a determination has to be made immediately whether to shut down the entire production line so as to prevent accumulation of excessive numbers of incomplete workpieces around the out-of-stock machine or whether to temporarily bypass the out-of-stock machine X and to reroute workpieces to other workstations. If the latter course of action is chosen, the management system should issue a request to an inventory system for additional machine-X stock and find out how much time it will take to receive the machine X stock so that it can calculate/control the amount of unfinished inventory that will be allowed to build up around the out-of-stock machine X. The decision calls for expert analysis and judgment.
The decision making responsibilities of the system do not stop at this first question but rather grow more complex as one realizes that the management system might be expected to further consider, as would a human manager, the question of whether the issued request for additional stock has been received by the inventory system and whether the inventory system is responding appropriately (expeditiously) to that request. A large maze of other questions can grow from the first set of posed questions as further aspects of the management operation are considered.
It can be appreciated that a fairly sophisticated management system might be needed to handle all the complications which could evolve on a factory line and that expert-system technology could be advantageously applied to design such a sophisticated management system.
Previously devised expert systems have been unable to fully meet the challenge of real time factory management. The general-purpose architectures of commercially available expert-systems (i.e., so-called expert "shells") are designed to generically process all types of symbolic relationships and this generalism often makes them too slow to be able to respond in timely fashion to real time developments on a factory floor.
An application-specific expert control system for the real time management of automated factory production lines and a method for developing the same have been proposed by the Ultimate Media Enterprises Corporation of Larkspur, California (hereafter "UME"). The UME system/method is based on a four-state reasoning paradigm wherein the "value" of postulated variables such as "insertion-machine-x-has-run-out-of-stock" or "the-PLC-of-insertion-machine-x-is-malfunctioning" are restricted to being either true (T), false (F), untested (U) or indeterminate even though tested (I).
Relational formulations (if-then constructs) having a form such as: --"machine-X-is-out-of-stock" is true (T) IF "the-PLC-of-machine-X-is-malfunctioning" is false (F) AND "out-of-stock-message-received-from-machine-X" is true (T)--are accumulated in a computer memory, according to the UME method, to create a rule base tree.
A rule base tree can be diagrammed to have the form of a natural tree, including roots, branches and nodes at which one branch joins with another. The values of unique variables are each located at a specific node. Variables whose values are not logical functions of other variables in the tree, but rather direct functions of PLC provided messages, can be visualized as defining bottom roots of the rule base tree. Variables whose states are indirectly determined by the values at the roots but whose states do not affect further (higher) variables in the tree can be visualized as defining branch tips of the tree. The logical operators which link the roots directly or indirectly to the branch tips can be visualized as defining branches and subbranches.
In the UME system, an "inferencing engine" works its way downwardly through a maze of branches and sub-branches in the rule base tree, from a variable (branch node) whose factual status is unknown but needs to be resolved (a so-called "hypothesis" or "goal" variable), toward the roots in order to find a path which will enable the engine to resolve the value of that unknown variable. In working its way down the tree, the inferencing engine identifies other unknown variables of the tree upon which the value of the "hypothesis" is predicated and designates these other variables as sub-goals. The value of a hypothesis variable at the top of the tree is derived by finding at least one path linking predicate tree roots which have known T or F values to the hypothesis, and performing prespecified logical function operations on these predicate roots to thereby establish the T or F values of other variables higher up on the one path. The T or F establishing process continues up the linking path in the tree until the factual status (T or F) of the goal and its predicate subgoals is resolved.
Lower tree variables can be diagrammed as being coupled to higher tree variables by the tree branches and the tree branch couplings between the variables can be viewed as defining the various logical operations such as AND, OR and NOT which are to be performed in order to establish the value of a higher variable on the basis of lower variables.
It can be appreciated that once the values of the roots in a rule base tree are established, the effects of their states can be propagated upwardly through the tree along a continuous path linking the roots to the branch tips by performing the branch-defined logical operations (AND, OR, NOT) of the path that couple unresolved variables to preresolved predicate variables below them. According to the UME approach, this upward propagation of branch-defined operations is limited to occurring only once--in order to maximize the speed at which the expert system traverses through the maze of paths in a tree and reaches a conclusion. A variable can never be considered untested (U) according to the UME algorithm after an attempt is made to evaluate it. This will be explained more fully later on.
In accordance with the UME method, a rule base tree is formed by compiling branches (AND/OR/NOT, mutual-exclusive formulations) and linking them to one another. There is a fixed limitation on the number of logical variables (256) which the UME system can handle and also on the number (15) of antecedent variables and/or logical operators which may be listed in the righthand side of each AND/OR formulation (i.e., A=B&C!D&E!F&G. . .). The branches and subbranches of a rule base tree are defined and linked by a knowledge-building team comprised of at least one human expert and one human computer programmer. The human programmer is expected to possess expert knowledge about the computer language and algorithms that are used to implement both the rule base and the inferencing engine while the human expert is expected to possess expertise about the factory production line that is to be managed and preferred ways of managing the line. The members of the team are supposed to work together in a highly cooperative manner to combine their individual areas of expertise, and from such combination, build a computer-usable data base which will define an error-free intelligence-providing rule base for a predefined "inferencing engine". One reason that a human programmer is usually required on the knowledge-building team is because the UME rule-base constructing language consists of numerically coded commands rather than English-like instructions which could be readily understood by persons who have not memorized a long list of numeric command codes.
When the team-constructed rule base is completed, it is coupled to the predefined inferencing-engine and the inferencing-engine is activated to begin evaluating the states (T,F,U,I) of preselected variables (hypotheses) within the rule base tree in accordance with "facts" that are inferred from data supplied by external sensors. The inferred states (T, F, U or I) of "goal" variables near the top of the rule base tree are ultimately supplied to if-then "command" constructs. The command constructs determine what course of action or nonaction the expert control system will choose to follow in response to perceived conditions on the factory floor.
While the expert control arrangement described above should work nicely from the purely theoretical point of view, the problems of real-world factory environments have to be considered in more detail.
One problem which is often overlooked, but needs consideration, is how to establish a reasonable balance between the cost of an expert control system (hereafter also referred to as an "ECS") and the speed at which the expert control system performs its decision-making operations. If the cost of the expert control system is unreasonably high because a very expensive "super computer" (i.e., a Cray machine) is needed for quickly executing certain AI operations, or because a large amount of development work is needed to generate the AI functions, it may be economically preferable to use one or more human experts to manage the production floor instead of the very expensive expert system. On the other hand, if the cost of the ECS is kept relatively low, but the decision-making speed and intelligence of the ECS suffer because low speed hardware was employed to reduce price, it may be that the expert control system will not be able to make decisions quickly enough to keep pace with real time developments on the factory production line, and as a result, the ECS will be worthless.
In order to achieve an acceptable balance in the price/performance ratio, the UME expert system was constructed with the above-described four level reasoning paradigm (T,F,U,I) and was further constructed to execute the inferencing operation on a low-priced computer based on the MOS Tech. 6502 microprocessor clocked at 3 MHz.
The UME inferencing engine was restricted to evaluating variables as few times as possible in order to optimize its price/performance ratio. This was achieved by holding constant the true or false (T or F) state of a variable once the value of the variable had risen from a previous (lower) "nonfactual" status of being either untested (U) or indeterminate (I) to a (higher) "factual" status of being conclusively either T or F (fact establishment). It was further achieved by preventing variables from being considered untested (U) after the inferencing engine scans by them once and attempts to establish their factual value. Once-scanned variables are forced to a value of at least indeterminate (I) if not (T) or (F). By omitting further evaluation of variables whose "factual state" (T or F) has already been conclusively established, and identifying all once-scanned variables as indeterminate (I), it was thought that the speed of downward path-finding and upward inferencing could be enhanced and that a commercially feasible price/performance ratio could be achieved.
It turns out that such a speed-enhancing strategy is not in keeping with some of the "real world" conditions which can suddenly develop on a factory production line.
By way of example, if the PLC of a particular workstation X (in an array of hundreds of workstations) begins to suddenly malfunction after the expert control system has already tested that PLC and has already established it to be a conclusive "fact" that the PLC is functioning properly, all inferencing decisions based on the constant state (T) of a variable "PLC-of-machine-X-is-properly-functioning" will be incorrect. (A sudden change of condition could occur for example, by virtue of a human operator manually switching control buttons on the particular machine X, or by virtue of a power supply fuse blowing due to a random power surge.)
By way of further example, if a PLC malfunctions and the ECS correctly sets a status variable "PLC-of-machine-X-is-properly-functioning" to false (F), but then corrective action is taken to bring that PLC back into operation, it is very difficult to reorient the ECS so it realizes the PLC is now functioning properly, because once set to a factual status of false (F), there is no simple mechanism other than a full restart for switching the status variable to the untested (U) value so as to invoke retesting of the now erroneous conclusion (that it is false (F)).
Because the basic strategy of the UME approach cannot accept such contingencies, it has been found that UME-type ECS's tend to lose track of what is actually occurring on the factory floor, and that the actions taken by expert control systems of this type are other than those desired. There remains a need, at least within the automated factory industry, for an expert control system which can be constructed to provide a reasonable balance between price/performance, and which at the same time can deal with the fast-changing "facts" of real world situations.
Another problem found to arise under the UME approach is that at least one human expert and one human computer programmer are required to interact as a tightly-knit team for generating the rule base tree. If the team is to operate efficiently, the human expert must know how to expeditiously communicate abstract rule concepts to the computer programmer and the computer programmer must be able to quickly learn the abstract concepts and then accurately translate such concepts into a machine-understandable data base. In cases where the inferencing engine is unable to perform some of the things desired by the human expert, because of inherent machine limitations or language constraints, the programmer has to be able to recognize this inability and convince the expert that such is the situation. The expert then has to modify his or her thinking patterns to match the capabilities of the machine and communicate a new set of abstract concepts to the programmer.
This knowledge building process can be both time consuming and expensive; especially so in cases where more than two highly skilled individuals might be needed for each step of the knowledge-building process. If there is a break anywhere in the chain of expert-to-programmer-to-machine communication, it is likely that a flaw (bug) will appear in the resultant rule-base tree (data base) and that the resultant expert control system will make incorrect choices. Dependency on this kind of long chained communication is undesirable.
There is yet a further problem with the way that a rule-base tree is developed by the UME method. Under the UME approach, the only way to determine whether a teamcreated rule base is correct (i.e., to determine that it doesn't include "bugs"), is to load an operative expert control system with such a rule base, connect the expert control system directly to the factory management network, and observe the results in real time on the production floor. If errors exist in the rule base, significant damage can occur on the production line. Also, substantial production time may be lost if lengthy real-time debugging is required. A need exists for a method of developing and testing a rule base without applying the same directly to a real time production line and without having to rely on continuous communication between a human expert and a human computer programmer.